package com.chj.zhongji.class04;

import java.util.HashMap;
import java.util.Map;

public class Code03_SnacksWays {
//	https://www.nowcoder.com/questionTerminal/1eddaa5e5eed4fd487aac0477afe5518?f=discussion
//	https://github.com/cherryljr/NowCoder/blob/master/%E7%89%9B%E7%89%9B%E7%9A%84%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98.java
	public static int ways1(int[] arr, int w) {
		return process(arr, 0, w);
	}

	// int[] arr = { 4, 3, 2, 9 };
	// int w = 8;
	public static int process(int[] arr, int index, int rest) {
		System.out.println();
		System.out.println("==sss===" + index + "==sss===" + rest);
		System.out.println();
		if (rest < 0) {
			System.out.println("==sss=<0==" + index + "==sss===" + rest);
			return -1;
		}
		if (index == arr.length) {
			System.out.println(arr.length + "==sss=arr.length==" + index + "==sss===" + rest);
			return 1;
		}

		int next1 = process(arr, index + 1, rest);

		int next2 = process(arr, index + 1, rest - arr[index]);

		System.out.println();
		System.out.println(arr[index] + "==next1: " + next1 + "===next2: " + next2);
		return next1 + (next2 == -1 ? 0 : next2);

	}

	public static int ways2(int[] arr, int w) {
		int N = arr.length;
		int[][] dp = new int[N + 1][w + 1];
		for (int j = 0; j <= w; j++) {
			dp[N][j] = 1;
		}
		for (int i = N - 1; i >= 0; i--) {
			for (int j = 0; j <= w; j++) {
				dp[i][j] = dp[i + 1][j] + ((j - arr[i] >= 0) ? dp[i + 1][j - arr[i]] : 0);
			}
		}
		return dp[0][w];
	}

	public static int ways3(int[] arr, int w) {
		int N = arr.length;
		int[][] dp = new int[N][w + 1];
		for (int i = 0; i < N; i++) {
			dp[i][0] = 1;
		}
		if (arr[0] <= w) {
			dp[0][arr[0]] = 1;
		}
		for (int i = 1; i < N; i++) {
			for (int j = 1; j <= w; j++) {
				dp[i][j] = dp[i - 1][j] + ((j - arr[i]) >= 0 ? dp[i - 1][j - arr[i]] : 0);
			}
		}
		int ans = 0;
		for (int j = 0; j <= w; j++) {
			ans += dp[N - 1][j];
		}
		return ans;
	}

	public static long ways4(long[] arr, long w) {
		int N = arr.length;
//		int[][] dp = new int[N + 1][w + 1];
		Map<Long, Map<Long, Long>> dp = new HashMap<>();
		for (int i = 0; i < N + 1; i++) {
			Map<Long, Long> tmp = new HashMap<>();
			for (int j = 0; j < w + 1; j++) {
				tmp.put((long) j, (long) 0);
			}
			dp.put((long) i, tmp);
		}
		for (int j = 0; j <= w; j++) {
//			dp[N][j] = 1;
			dp.get((long) N).put((long) j, (long) 1);
		}
		for (int i = N - 1; i >= 0; i--) {
			for (int j = 0; j <= w; j++) {
//				dp[i][j] = dp[i + 1][j] + ((j - arr[i] >= 0) ? dp[i + 1][j - arr[i]] : 0);
				dp.get((long) i).put((long) j, dp.get((long) (i + 1)).get((long) j));
				if (j >= arr[i]) {
					dp.get((long) i).put((long) j,
							dp.get((long) i).get((long) j) + dp.get((long) (i + 1)).get((long) (j - arr[i])));
				}
			}
		}
//		return dp[0][w];
		return dp.get((long) 0).get(w);
	}

	public static int ways5(int[] nums, int target) {
		int N = nums.length;
		int[][] dp = new int[N + 1][target + 1];
		for (int j = 0; j <= target; j++) {
			dp[N][j] = 1;
		}
		for (int i = N - 1; i >= 0; i--) {
			for (int j = 0; j <= target; j++) {
				dp[i][j] = dp[i + 1][j] + ((j - nums[i] >= 0) ? dp[i + 1][j - nums[i]] : 0);
			}
		}
		return dp[0][target];
	}

	public static void main(String[] args) {
		int[] arr = { 4, 3, 2, 9 };
		int w = 8;

		long[] arr2 = { 4, 3, 2, 9 };
		long w2 = 8;
		System.out.println(ways1(arr, w));
		System.out.println(ways2(arr, w));
		System.out.println(ways3(arr, w));
		System.out.println(ways4(arr2, w2));
	}
}
